package leetcode3;
import java.util.*;

public class Day10 {






    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> grid = new ArrayList<>();
        ArrayList<Integer> a1 = new ArrayList<>();
        a1.add(2);
        a1.add(1);
        a1.add(1);
        grid.add(a1);
        ArrayList<Integer> a2 = new ArrayList<>();
        a2.add(1);
        a2.add(0);
        a2.add(1);
        grid.add(a2);
        ArrayList<Integer> a3 = new ArrayList<>();
        a3.add(1);
        a3.add(1);
        a3.add(1);
        grid.add(a3);
        rotApple(grid);
    }


    public static int rotApple (ArrayList<ArrayList<Integer>> grid) {
        // write code here
        //1.第一次遍历数组，记录“腐蚀的苹果”
        //2.开始层序遍历
        boolean[][] check;
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        int m,n;
        Queue<int[]> queue = new LinkedList<>();
        m=grid.size();n=grid.get(0).size();
        check = new boolean[m][n];
        int ret = 0;//记录好苹果的数量
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid.get(i).get(j) == 2) {
                    queue.add(new int[]{i,j});
                    check[i][j]=true;
                }else if(grid.get(i).get(j) == 1) {
                    ret++;
                }
            }
        }
        int level=0;//记录扩展的层数（分钟）
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- != 0) {
                int[] tmp = queue.poll();
                //腐蚀四周的好苹果
                for(int k=0;k<4;k++) {
                    int x = tmp[0]+dx[k];
                    int y = tmp[1]+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n && !check[x][y] &&grid.get(x).get(y)==1) {
                        queue.add(new int[]{x,y});
                        check[x][y]=true;
                        ret--;
                    }
                }
            }
            level++;
        }
        return ret==0?level:-1;
    }



    /**
     * 游游的you
     * @param args
     */
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int q = in.nextInt();
            int[][] nums = new int[q][3];
            for(int i=0;i<q;i++) {
                for(int j=0;j<3;j++) {
                    nums[i][j] = in.nextInt();
                }
            }
            for(int i=0;i<q;i++) {
                int y=nums[i][0],o=nums[i][1],u=nums[i][2];
                int sum1 = Math.min(y,Math.min(o,u)) * 2;
                int sum2 = o - Math.min(y,Math.min(o,u)) - 1;
                if(sum2>0) {
                    System.out.println(sum1+sum2);
                }else {
                    System.out.println(sum1);
                }
            }
        }
    }

    /**
     * 杨辉三角
     * @param args
     */
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[][] nums = new int[n][n];

            for(int i=0;i<n;i++) {
                for(int j=0;j<=i;j++) {
                    if(i==j || j==0) nums[i][j] = 1;
                    else {
                        nums[i][j] = nums[i-1][j-1] + nums[i-1][j];
                    }
                }
            }

            for(int i=0;i<n;i++) {
                for(int j=0;j<=i;j++) {
                    System.out.printf("%5d",nums[i][j]);

                }
                System.out.println();
            }

        }
    }




    /**
     * 单词搜索
     */
    boolean[][] check;
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};
    int m,n;
    public boolean exist (String[] board, String word) {
        // write code here
        m=board.length;n=board[0].length();
        check = new boolean[m][n];
        for(int i=0;i<board.length;i++) {
            for(int j=0;j<board[0].length();j++) {
                if(board[i].charAt(j) == word.charAt(0)) {
                    check[i][j]=true;
                    if(dfs(board,i,j,word,1)) return true;
                    check[i][j]=false;
                }
            }
        }
        return false;
    }

    public boolean dfs(String[] board,int i,int j,String word,int pos) {
        if(pos == word.length()) return true;

        for(int k=0;k<4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x>=0&&x<m && y>=0&&y<n && !check[x][y] && word.charAt(pos)==board[x].charAt(y)) {
                check[x][y]=true;
                if(dfs(board,x,y,word,pos+1)) return true;
                else check[x][y]=false;
            }
        }
        return false;
    }


    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int N = in.nextInt();
            //找出前后两个数
            int a = 0,b=1,c=0;
            while(c<N) {
                c = a+b;
                a = b;
                b = c;
            }
            System.out.println();
            // a <= N <=b
            System.out.println(Math.min(Math.abs(a-N),Math.abs(b-N)));
        }
    }
}
